package 二叉树;

public class No117填充每个节点的下一个右侧节点指针II {

    /**
     * 给定一个二叉树
     * struct Node {
     *   int val;
     *   Node *left;
     *   Node *right;
     *   Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * 初始状态下，所有 next 指针都被设置为 NULL。
     *
     * 进阶：
     * 你只能使用常量级额外空间。
     * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
     *  
     * 示例：
     * 输入：root = [1,2,3,4,5,null,7]
     * 输出：[1,#,2,3,#,4,5,7,#]
     * 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
     *  
     * 提示：
     * 树中的节点数小于 6000
     * -100 <= node.val <= 100
     */

    //非满二叉树版
    public Node connect(Node root) {

        Node head=root;
        Node last=root;

        while (head!=null){

            Node temp=head;

            while (head!=null){

                //左右不为空,则直接连接
                if(head.left!=null&&head.right!=null){
                    head.left.next=head.right;

                    this.connectChild(head,head.right);

                }

                //左不为空
                else if(head.left!=null){

                    this.connectChild(head,head.left);

                }

                //右不为空
                else if(head.right!=null){

                    this.connectChild(head,head.right);

                }

                //左右都为空
                else{

                    //什么都不做

                }

                //去右边
                if(last!=null) {
                    last = last.next;
                }
                head=head.next;

            }

            //去下一层
            //当前节点可以直接到达下一层
            if(temp.left!=null||temp.right!=null) {
                last = temp;
                head = temp.left == null ? temp.right : temp.left;
            }else{
                //不可直接到达,所以找到第一个左右孩子不为空的节点,才能下一层
                while (temp!=null&&temp.left==null&&temp.right==null){
                    temp=temp.next;
                }
                last=temp;
                head = temp!=null? temp.left == null ? temp.right : temp.left:null;
            }

        }

        return root;
    }

    //连接孩子节点
    private void connectChild(Node last, Node node) {

        Node next=last.next;

        while (next!=null){

            if(next.left!=null||next.right!=null){
                break;
            }
            next=next.next;

        }

        if(next==null){
            return;
        }

        if(next.left!=null){
            node.next=next.left;
        } else {
            node.next=next.right;
        }

    }

    public static void main(String[] args) {
        No117填充每个节点的下一个右侧节点指针II n=new No117填充每个节点的下一个右侧节点指针II();

        Node n1=new Node(-1);
        Node n2=new Node(-7);
        Node n3=new Node(9);
        Node n4=new Node(-1);
        Node n5=new Node(-7);
        Node n6=new Node(8);
        Node n7=new Node(9);

        n1.left=n2;
        n1.right=n3;
        n3.left=n4;
        n3.right=n5;
        n4.right=n6;
        n5.left=n7;

        Node result = n.connect(n1);

        System.out.println(result.val);
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

}
